package com.yan.programercode.chapter_1.question_5;

import java.util.Arrays;
import java.util.Stack;

/**
 * 一个栈中元素为整形，现在想将该栈从顶到底按照从大到小的顺序进行排序，只允许申请一个栈。
 * 除此之外可以身亲给新的变量，但不允许申请新的数据结构，如何完成排序？
 * 
 * @author Yan
 *
 */
public class StackSort {

	public static void main(String[] args) {
		sortStack();
		sortStack2();
	}
	
	public static Stack<Integer> initStack(){
		// [2,5,8,0,1,3,9,7,6,4]
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(2);
		stack.push(5);
		stack.push(8);
		stack.push(0);
		stack.push(1);
		stack.push(3);
		stack.push(9);
		stack.push(7);
		stack.push(6);
		stack.push(4);
		return stack;
	}

	public static void sortStack(){
		// [2,5,8,0,1,3,9,7,6,4]
		Stack<Integer> stack = initStack();
		Stack<Integer> help = new Stack<Integer>();

		// 因为待排序栈要排序成从栈顶到栈底由大到小，那么辅助栈中从栈顶到栈底应该是由小到大
		
		while(!stack.isEmpty()){
			int current = stack.pop();
			// 辅助栈空的时候，直接将当前值压入辅助栈
			if(help.isEmpty()){
				help.push(current);
			}else{
				if(current < help.peek()){
					help.push(current);
				}else{
					// 存在一种情况，就是current比help中所有元素都要大，那么help弹空也在help中找不到比current大的元素，
					// 此时current最大，应该将current压入空的help栈
					boolean currentPushIntoHelp = false;
					while(!help.isEmpty()){
						if(current <= help.peek()){
							help.push(current);
							currentPushIntoHelp = true;
							break;
						}else{
							int topInHelp = help.pop();
							stack.push(topInHelp);
						}
					}
					
					// 
					if(!currentPushIntoHelp){
						help.push(current);
					}
				}
			}
		}
		
		while(!help.isEmpty()){
			int current = help.pop();
			stack.push(current);
		}
		
		System.out.println(Arrays.toString(stack.toArray()));
	}
	
	public static void sortStack2(){
		// [2,5,8,0,1,3,9,7,6,4]
		Stack<Integer> stack = initStack();
		Stack<Integer> help = new Stack<Integer>();
		
		while(!stack.isEmpty()){
			int cur = stack.pop();
			
			// 将help栈中比cur小于等于的元素都弹出并压入stack
			// 保证help中元素没有小于等于cur的
			while(!help.isEmpty() && cur > help.peek()){
				stack.push(help.pop());
			}
			help.push(cur);
		}
		
		while(!help.isEmpty()){
			stack.push(help.pop());
		}
		System.out.println(Arrays.toString(stack.toArray()));
	}
	
}
